// file MaxHeap.h

#ifndef MC_HEAP_H
#define MC_HEAP_H

#include<stdlib.h>
#include <iostream>

template<class T>
class MinHeap {
public:
	MinHeap(int MinHeapSize = 500);
	~MinHeap();
	void	Clear(void){ CurrentSize = 0; };
	int Size() const { return CurrentSize; }
	T Min() { return heap[1]; }
	T& Insert(const T& x);
	bool DeleteMin(T& x);
	void Initialize(T a[], int size, int ArraySize);
	void Deactivate() { heap = 0; }
	void Output() const;
	void Empty(void);
private:
	int CurrentSize, MaxSize;
	T *heap; // element array
};

template<class T>
MinHeap<T>::~MinHeap()
{
	if (heap != NULL)
		delete[] heap;
}

template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{// Min heap constructor.
	MaxSize = MinHeapSize;
	heap = new T[MaxSize + 1];
	CurrentSize = 0;
}

template<class T>
void MinHeap<T>::Empty(void)
{
	CurrentSize = 0;
}

template<class T>
T& MinHeap<T>::Insert(const T& x)
{// Insert x into the min heap.
	// find place for x
	// i starts at new leaf and moves up tree
	int i = ++CurrentSize;
	while (i != 1 && heap[i / 2]>x) {
		// cannot put x in heap[i]
		heap[i] = heap[i / 2]; // move element down
		i /= 2; // move to parent
	}
	heap[i] = x;

	return (heap[i]);
}

template<class T>
bool MinHeap<T>::DeleteMin(T& x)
{// Set x to min element and delete
	// min element from heap.
	// check if heap is empty
	if (CurrentSize<1)
		return false;

	x = heap[1]; // min element

	// restructure heap
	T y = heap[CurrentSize--]; // last element

	// find place for y starting at root
	int i = 1,  // current node of heap
		ci = 2; // child of i
	while (ci <= CurrentSize) {// find place to put y
		// heap[ci] should be smaller child of i
		if (ci < CurrentSize &&
			heap[ci] > heap[ci + 1]) ci++;

		// can we put y in heap[i]?
		if (y <= heap[ci]) break;  // yes

		// no
		heap[i] = heap[ci]; // move child up
		i = ci;  // move down a level
		ci *= 2;
	}
	heap[i] = y;

	return true;
}

template<class T>
void MinHeap<T>::Initialize(T a[], int size, int ArraySize)
{// Initialize min heap to array a.
	delete[] heap;
	heap = a;
	CurrentSize = size;
	MaxSize = ArraySize;

	// make into a min heap
	for (int i = CurrentSize / 2; i >= 1; i--) {
		T y = heap[i]; // root of subtree

		// find place to put y
		int c = 2 * i; // parent of c is target
		// location for y
		while (c <= CurrentSize) {
			// make c point to smaller sibling
			if (c < CurrentSize &&
				heap[c].p > heap[c + 1].p) c++;

			// can we put y in heap[c/2]?
			if (y.p <= heap[c].p) break;  // yes

			// no
			heap[c / 2] = heap[c]; // move heap[c] up
			c *= 2;              // move c down a level
		}
		heap[c / 2] = y;
	}
}

template<class T>
void MinHeap<T>::Output() const
{
}


template<class T>
class MaxHeap {
   public:
      MaxHeap(int MaxHeapSize = 500);
      ~MaxHeap() {delete [] heap;}
	  void	Clear(void){CurrentSize=0;};
      int Size() const {return CurrentSize;}
      T Max() {if (CurrentSize == 0)
                  throw OutOfBounds();
               return heap[1];}
      MaxHeap<T>& Insert(const T& x);
      bool DeleteMax(T& x);
      void Initialize(T a[], int size, int ArraySize);
      void Deactivate() {heap = 0;}
      void Output() const;
   private:
      int CurrentSize, MaxSize;
      T *heap;  // element array
};

template<class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize)
{// Max heap constructor.
   MaxSize = MaxHeapSize;
   heap = new T[MaxSize+1];
   CurrentSize = 0;
}

template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x)
{// Insert x into the max heap.
   if (CurrentSize == MaxSize)
	   return *this;

   // find place for x
   // i starts at new leaf and moves up tree
   int i = ++CurrentSize;
   while (i != 1 && heap[i/2]<x) {
      // cannot put x in heap[i]
      heap[i] = heap[i/2]; // move element down
      i /= 2;              // move to parent
      }

   heap[i] = x;
   return *this;
}

template<class T>
bool MaxHeap<T>::DeleteMax(T& x)
{// Set x to max element and delete
 // max element from heap.
   // check if heap is empty
   if (CurrentSize == 0)
	   return false;

   x = heap[1]; // max element

   // restucture heap
   T y = heap[CurrentSize--]; // last element

   // find place for y starting at root
   int i = 1,  // current node of heap
       ci = 2; // child of i
   while (ci <= CurrentSize) {
      // heap[ci] should be larger child of i
      if (ci < CurrentSize &&
          heap[ci] < heap[ci+1]) ci++;

      // can we put y in heap[i]?
      if (y >= heap[ci]) break;   // yes

      // no
      heap[i] = heap[ci]; // move child up
      i = ci;             // move down a level
      ci *= 2;
      }
   heap[i] = y;

   return true;
}

template<class T>
void MaxHeap<T>::Initialize(T a[], int size,
                               int ArraySize)
{// Initialize max heap to array a.
   delete [] heap;
   heap = a;
   CurrentSize = size;
   MaxSize = ArraySize;

   // make into a max heap
   for (int i = CurrentSize/2; i >= 1; i--) {
      T y = heap[i]; // root of subtree

      // find place to put y
      int c = 2*i; // parent of c is target
                   // location for y
      while (c <= CurrentSize) {
         // heap[c] should be larger sibling
         if (c < CurrentSize &&
             heap[c] < heap[c+1]) c++;

         // can we put y in heap[c/2]?
         if (y >= heap[c]) break;  // yes

         // no
         heap[c/2] = heap[c]; // move child up
         c *= 2; // move down a level
         }
      heap[c/2] = y;
      }
}

template<class T>
void MaxHeap<T>::Output() const
{
   cout << "The " << CurrentSize
        << " elements are"<< endl;
   for (int i = 1; i <= CurrentSize; i++)
       cout << heap[i] << ' ';
   cout << endl;
}

#endif
